
import java.util.ArrayList;
import java.util.List;


/**
 * @Author @fiber-cloud
 * @Date 2025/10/18 16:29
 */
public class T2025_10_18 {
    //链接：https://ac.nowcoder.com/acm/contest/19850/A
    //来源：牛客网
    // 老李见和尚赢了自己的酒，但是自己还舍不得，所以就耍起了赖皮
    // 对和尚说，光武不行，再来点文的，你给我说出来1-8的全排序，我就让你喝，
    // 这次绝不耍你，你能帮帮和尚么？
    public static void main(String[] args) {
        //没有输入，只有输出，输出1~8的全排列
        int[] nums = {1,2,3,4,5,6,7,8};
        List<List<Integer>> lists = permute(nums);
        
        //输出所有的排列
        for (List<Integer> p : lists) {
            for (int num : p) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }

    //利用回溯生成排列
    private static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res =  new ArrayList<>();

        backtrack(nums,new ArrayList<>(),new boolean[nums.length],res);
        return res;
    }

    private static void backtrack(int[] nums, List<Integer> cur, boolean[] booleans, List<List<Integer>> res) {
        //如果当前排列长度等于数组长度，说明已经完成了一个排列,此时保存结果
        if (cur.size() == nums.length){
            res.add(new ArrayList<>(cur));
            return;
        }

        //遍历所有的可能选择
        for (int i = 0; i < nums.length; i++) {
            //如果数字已经被使用过，则跳过该数字
            if (booleans[i]){
                continue;
            }
            //做出选择
            booleans[i] = true;//被使用后置为true
            cur.add(nums[i]);

            //递归进入下一层
            backtrack(nums,cur,booleans,res);

            //撤销选择
            booleans[i] = false;
            cur.remove(cur.size()-1);
        }
    }

}
